Various techniques are used to help computer memory access speeds keep up with increases in computer processor speeds. For example, these techniques may include applying loop and data transformations to improve the locality of data referenced by a computer program. Specifically, compilers may apply loop fusions, linear loop transformations, loop distributions, array contractions, and many other transformations to increase memory access speed.
Specifically regarding loop fusion, this technique involves, for example only, combining two or more loops to form a single loop (or fewer loops). Loop fusion may take advantage of the proximity of data referenced in loops that are located adjacent to one another in program code. Loop fusion may combine the cache context of multiple loops into a single new loop. Thus, data accessed by various nested loops (i.e., a loop embedded in another loop) may, after loop fusion, be accessed from within the same new nested loop, thereby potentially reducing the number of memory accesses. Loop fusion may increase opportunities for reducing the overhead of array references by replacing them with references to compiler-generated scalar variables. Loop fusion may also improve the effectiveness of data prefetching. Certain other transformations such as linear loop transformations, loop peeling, and loop alignment can expose more opportunities for loop fusion.
Data access behavior with memory optimizations and memory reuse can be further optimized across procedures (e.g., named sequence of statements that usually performs a single task), loops, and IF statements. For example, IF and ELSE statements may be merged together thereby enabling loop fusion. IF statement merging involves, for example only, combining two or more IF statements (e.g., IF-nests) into a single IF-nest (or fewer nests). The fused loop may then improve reuses of memory references and avoid redundant computations.